import java.util.Arrays;

/**
 * 冒泡排序
 * */
public class BubbleSort {
    public static void main(String[] args) {
//        int[] a = {5, 2, 7, 4, 1, 3, 8, 9};
        int[] a = {1, 2, 3, 4, 5, 7, 8, 9};
        bubble_v2(a);
    }

    /**
     * 算法描述：
     * <p>
     * 1. 依次比较数组中相邻两个元素大小，若 a[j] > a[j+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后
     * <p>
     * 2. 重复以上步骤，直到整个数组有序
     * <p>
     * 优化点：
     * <p>
     * 1、每经过一轮冒泡，内层循环就可以减少一次
     * <p>
     * 2、如果某一轮冒泡没有发生交换，则表示所有数据有序，可以结束外层循环
     */
    public static void bubble(int[] a) {
        for (int j = 0; j < a.length - 1; j++) {
            // 一轮冒泡
            boolean swapped = false; // 是否发生了交换
            for (int i = 0; i < a.length - 1 - j; i++) {
                System.out.println("比较次数" + i);
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                    swapped = true;
                }
            }
            System.out.println("第" + j + "轮冒泡"
                    + Arrays.toString(a));
            if (!swapped) {
                break;
            }
        }
    }

    /**
     * 进一步改冒泡排序算法：
     * <p>
     * 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，
     * 如果这个值为零，表示整个数组有序，直接退出外层循环即可
     */
    public static void bubble_v2(int[] a) {
        int n = a.length - 1;
        while (true) {
            int last = 0; // 表示最后一次交换索引位置
            for (int i = 0; i < n; i++) {
                System.out.println("比较次数" + i);
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                    last = i;
                }
            }
            n = last;
            System.out.println("第轮冒泡"
                    + Arrays.toString(a));
            if (n == 0) {
                break;
            }
        }
    }

    public static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

}
